import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2020/7/5 上午 10:20
 */
public class month2007 {

    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        int num = arr[1] - arr[0];
        for (int i = 2; i < arr.length; i++) {
            int thisNum = arr[i] - arr[i - 1];
            if (thisNum != num) {
                return false;
            }
        }
        return true;
    }

    public int getLastMoment(int n, int[] left, int[] right) {
        int ret = 0;
        if (left.length != 0) {
            Arrays.sort(left);
            ret = left[left.length - 1];
        }
        if (right.length != 0) {
            Arrays.sort(right);
            ret = Math.max(ret, n - right[0]);
        }
        return ret;
    }

    public int numSubmat(int[][] mat) {
        int rows = mat.length;
        int columns = mat[0].length;
        int ret = 0;
        int[][] sums = new int[rows + 1][columns + 1];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + mat[i][j];
            }
        }
        ret = sums[rows][columns];
        for (int row = 1; row <= rows; row++) {
            for (int column = 1; column <= columns; column++) {
                for (int i = 1; i + row - 1 < sums.length; i++) {
                    for (int j = 1; j + column - 1 < sums[0].length; j++) {
                        if (row == 1 && column == 1) {
                            continue;
                        }
                        if (sums[i + row - 1][j + column - 1] - sums[i + row - 1][j - 1] - sums[i - 1][j + column - 1] + sums[i - 1][j - 1] == row * column) {
                            ret++;
                        }
                    }
                }
            }
        }
        return ret;
    }

    public String minInteger(String num, int k) {
        char[] chars = num.toCharArray();
        int length = chars.length;
        for (int i = 0; i < length && k > 0; ++i) {
            int cur = i;
            for (int j = i + 1; j < length && j - i <= k; ++j) {
                if (chars[j] < chars[cur]) {
                    cur = j;
                }
            }
            for (int j = cur; j > i && k > 0; --j) {
                k--;
                char t = chars[j];
                chars[j] = chars[j - 1];
                chars[j - 1] = t;
            }
        }
        return new String(chars);
    }

    public int numWaterBottles(int numBottles, int numExchange) {
        int ret = numBottles;
        while (numBottles > numExchange) {
            int use = numBottles / numExchange;
            int left = numBottles % numExchange;
            ret += use;
            numBottles = left + use;
        }
        ret += numBottles / numExchange;
        return ret;
    }

    public int[] countSubTrees(int n, int[][] edges, String labels) {
        ArrayList<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        int[] count = new int[26], sum = new int[n];
        boolean[] visited = new boolean[n];
        countSubTrees(0, visited, sum, count, graph, labels);
        return sum;
    }

    private void countSubTrees(int index, boolean[] visited, int[] sum, int[] count, ArrayList<Integer>[] graph, String labels) {
        if (!visited[index]) {
            visited[index] = true;
            for (int i : graph[index]) {
                int[] newCount = new int[26];
                countSubTrees(i, visited, sum, newCount, graph, labels);
                for (int j = 0; j < 26; j++) {
                    count[j] += newCount[j];
                }
                sum[index] += newCount[labels.charAt(index) - 'a'];
            }
            sum[index]++;
            count[labels.charAt(index) - 'a']++;
        }
    }

    public List<String> maxNumOfSubstrings(String s) {
        return null;
    }

    public int closestToTarget(int[] arr, int target) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (list.isEmpty() || i != list.get(list.size() - 1)) {
                list.add(i);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            int num = list.get(i);
            for (int j = i; j < list.size(); j++) {
                num &= list.get(j);
                ans = Math.min(ans, Math.abs(target - num));
                if (num <= target) {
                    break;
                }
            }
        }
        return ans;
    }

    public int minFlips(String target) {
        List<Integer> switchState = new ArrayList<>(target.length());
        for (Character character : target.toCharArray()) {
            switchState.add(Character.getNumericValue(character));
        }
        int res = 0;
        for (Integer state : switchState) {
            if (state == 0) {
                if (res % 2 == 1) {
                    res++;
                }
            } else {
                if (res % 2 == 0) {
                    res++;
                }
            }
        }
        return res;
    }

    /**
     * Definition for a binary tree node.
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int countPairs(TreeNode root, int distance) {
        if (root == null) {
            return 0;
        }
        return countPairs(root, distance, new int[distance]);
    }

    public int countPairs(TreeNode root, int distance, int[] distanceList) {
        if (root.left == null && root.right == null) {
            if (distance > 1) {
                distanceList[1]++;
            }
            return 0;
        } else if (root.left == null) {
            int res = countPairs(root.right, distance, distanceList);
            if (distance - 1 >= 0) {
                System.arraycopy(distanceList, 0, distanceList, 1, distance - 1);
            }
            return res;
        } else if (root.right == null) {
            int res = countPairs(root.left, distance, distanceList);
            if (distance - 1 >= 0) {
                System.arraycopy(distanceList, 0, distanceList, 1, distance - 1);
            }
            return res;
        } else {
            int res = 0;
            int[] distancesLeft = new int[distance];
            int[] distancesRight = new int[distance];
            res += countPairs(root.left, distance, distancesLeft);
            res += countPairs(root.right, distance, distancesRight);
            for (int i = distance - 1; i > 0; i--) {
                distanceList[i] = distancesLeft[i - 1] + distancesRight[i - 1];
            }
            for (int i = 1; i < distance; i++) {
                distancesRight[i] += distancesRight[i - 1];
                res += distancesLeft[distance - i] * distancesRight[i];
            }
            return res;
        }
    }

    public int getLengthOfOptimalCompression(String s, int k) {
        return 0;
    }

    public String restoreString(String s, int[] indices) {
        TreeMap<Integer, Character> treeMap = new TreeMap<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            treeMap.put(indices[i], chars[i]);
        }
        StringBuilder builder = new StringBuilder();
        for (Character character : treeMap.values()) {
            builder.append(character);
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        month2007 month2007 = new month2007();
        System.out.println(Arrays.toString(month2007.countSubTrees(4, new int[][]{{0, 1}, {1, 2}, {0, 3}}, "bbbb")));
    }
}
